package acm;

import java.util.Scanner;

/**
 * HDOJ 2154
 * @author Administrator
 *
 */
public class JumpCount {

	public static void main(String[] args) {
		//System.out.println(getComposition(5, 4));
		Scanner scanner =new Scanner(System.in);
		int inTemp;
		while ((inTemp=scanner.nextInt() )!=0) {
			System.out.println(getCount(inTemp));
		}
		scanner.close();
	}

	//动态规划的思想
	public static long getCount(int m) {
		int i = 0;
		int[][] d = new int[1001][3];
		//当跳一步且位于A的时候为0,位于B或者C都是种
		d[1][0] = 0;
		d[1][1] = d[1][2] = 1;
		for (i = 2; i <= m; i++) {
			d[i][0] = (d[i - 1][1]  + d[i - 1][2] ) % 10000;
			d[i][1] = (d[i - 1][0]  + d[i - 1][2] ) % 10000;
			d[i][2] = (d[i - 1][0] + d[i - 1][1] ) % 10000;
		}
		return d[m][0];
	}
	/*//受跳台阶的启发
	//思路就是每次走一阶或者两阶，走n次，n次的和为3的倍数
	public static long getCount(int m){
		if(m<=1){
			return 0;
		}
		//i为跳一次的次数
		int i=0;
		for(;i<=m;i++){
			if((2*m-i)%3==0){
				break;
			}
		}
		long result=0;
		for (; i <=m ; i+=3) {
			result+=getComposition(m,i)%1000;
		}
		return result;
	}
	//容易溢出，不适合解决m较大的情况
	public  static long getComposition(int n, int m) {
		if(m>n||m<0||n<0){
			return -1;
		}
		if(m==0){
			return 1;
		}
		long product=1;
		for(int i=1;i<=M; i++) {  
           product=product*(N-M+i)/i;  
        }  
        return sum;;
	}*/
}
